class Solution {
private:
    int left = 0, maxLen = 1;
    
public:
    /**
     * 
     * @param s string字符串 
     * @return string字符串
     */
    string longestPalindrome(string s) {
        // write code here
        int length = s.length();
        if (length < 2) return s;
        for (int i = 0; i < length; ++i) {
            findMax(s, i, i);
            findMax(s, i, i + 1);
        }
        return s.substr(left, maxLen);
    }
    
    void findMax(string &s, int i, int j) {
        int length = s.length();
        while (i >= 0 && j <= length - 1 && s[i] == s[j]) {
            i--; j++;
        }
        int len = j - i - 1;
        if (len > maxLen) {
            left = i + 1;
            maxLen = len;
        }
    }
};

class Solution2 {
public:
    string longestPalindrome(string s) {
        int length = s.length();
        if (length < 2) return s;
        int maxLeft = 0, maxLen = 1;
        vector<vector<int>> dp(length, vector<int>(length));
        for (int i = 0; i < length; ++i) {
            dp[i][i] = 1;
        }
        for (int L = 2; L <= length; ++L) {
            for (int i = 0; i < length - L + 1; ++i) {
                int j = i + L - 1;
                if (s[i] != s[j]) {
                    dp[i][j] = 0;
                } else {
                    if (j - i < 3)
                        dp[i][j] = 1;
                    else
                        dp[i][j] = dp[i + 1][j - 1];
                }
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    maxLeft = i;
                }
            }
        }
        return s.substr(maxLeft, maxLen);
    }
};
